package com.ruben.study;

import java.util.*;
import java.util.concurrent.atomic.AtomicReference;

/**
 * @ClassName: GreedyAlgorithmDemo
 * @Description: 我还没有写描述
 * @Date: 2020/11/22 0022 15:23
 * *
 * @author: <achao1441470436@gmail.com>
 * @version: 1.0
 * @since: JDK 1.8
 */
public class GreedyAlgorithmDemo {
    public static void main(String[] args) {
        // 所有广播电台
        Map<String, HashSet<String>> broadCasts = getBroadCasts();
        // 所有地区
        Set<String> allAreas = new HashSet<>();
        // 获得所有地区
        broadCasts.forEach((k, v) -> allAreas.addAll(v));
        // 最后结果
        List<String> result = new ArrayList<>();
        // 执行过程中电台覆盖的地区
        Set<String> tempSet = new HashSet<>();
        // 最优电台
        AtomicReference<String> maxKey = new AtomicReference<>();
        while (!allAreas.isEmpty()) {
            AtomicReference<String> finalMaxKey = maxKey;
            broadCasts.forEach((key, value) -> {
                tempSet.clear();
                tempSet.addAll(value);
                tempSet.retainAll(allAreas);
                if (!tempSet.isEmpty() &&
                        // 如果当前是最优解
                        (finalMaxKey.get() == null || tempSet.size() > broadCasts.get(finalMaxKey.get()).size())) {
                    finalMaxKey.set(key);
                }
            });
            // 最优解加入结果
            if (maxKey.get() != null) {
                result.add(maxKey.get());
                allAreas.removeAll(broadCasts.get(maxKey.get()));
                maxKey = new AtomicReference<>();
            }
        }
        result.forEach(System.out::println);
    }

    private static Map<String, HashSet<String>> getBroadCasts() {
        // 创建广播电台，放入map
        Map<String, HashSet<String>> broadCasts = new HashMap<>();
        // 将各个电台放入set
        HashSet<String> k1 = new HashSet<>(Arrays.asList("北京", "上海", "天津"));
        HashSet<String> k2 = new HashSet<>(Arrays.asList("广州", "北京", "深圳"));
        HashSet<String> k3 = new HashSet<>(Arrays.asList("成都", "上海", "杭州"));
        HashSet<String> k4 = new HashSet<>(Arrays.asList("上海", "天津"));
        HashSet<String> k5 = new HashSet<>(Arrays.asList("杭州", "大连"));
        // 加入到map
        broadCasts.put("K1", k1);
        broadCasts.put("K2", k2);
        broadCasts.put("K3", k3);
        broadCasts.put("K4", k4);
        broadCasts.put("K5", k5);
        return broadCasts;
    }
}
